Feb 94 Challenge
Volume Number: 10
Issue Number: 2
Column Tag: Programmers’ Challenge
Programmers’ Challenge 
By Nice Silk Man
Note: Source code files accompanying article are located on MacTech CD-ROM orsource code disks.
The Rules
Here’s how it works: Each month there will be a different programming challenge
presented here. First, you must write some code that solves the challenge. Second, you
must optimize your code (a lot). Then, submit your solution to MacTech Magazine
(formerly MacTutor). A winner will be chosen based on code correctness, speed, size
and elegance (in that order of importance) as well as the postmark of the answer. In
the event of multiple equally desirable solutions, one winner will be chosen at random
(with honorable mention, but no prize, given to the runners up). The prize for the
best solution each month is $50 and a limited edition “The Winner! MacTech Magazine
Programming Challenge” T-shirt (not to be found in stores).
In order to make fair comparisons between solutions, all solutions must be in
ANSI compatible C (i.e., don’t use Think’s Object extensions). Only pure C code can be
used. Any entries with any assembly in them will be disqualified (except for those
challenges specifically stated to be in assembly). However, you may call any routine
in the Macintosh toolbox you want (i.e., it doesn’t matter if you use NewPtr instead of
malloc). All entries will be tested with the FPU and 68020 flags turned off in THINK C.
When timing routines, the latest version of THINK C will be used (with ANSI Settings
plus “Honor ‘register’ first” and “Use Global Optimizer” turned on) so beware if you
optimize for a different C compiler. All code should be limited to 60 characters wide.
This will aid us in dealing with e-mail gateways and page layout.
The solution and winners for this month’s Programmers’ Challenge will be
published in the issue two months later. All submissions must be received by the 10th
day of the month printed on the front of this issue.
All solutions should be marked “Attn: Programmers’ Challenge Solution” and
sent to Xplain Corporation (the publishers of MacTech Magazine) via “snail mail” or
preferably, e-mail - AppleLink: MT.PROGCHAL, Internet: progchallenge@xplain.com,
CompuServe: 71552,174 and America Online: MT PRGCHAL. If you send via snail
mail, please include a disk with the solution and all related files (including contact
information). See page 2 for information on “How to Contact Xplain Corporation.”
MacTech Magazine reserves the right to publish any solution entered in the
Programming Challenge of the Month and all entries are the property of MacTech
Magazine upon submission. The submission falls under all the same conventions of an
article submission.
WE PRY ANY HEAP
Everyone likes anagrams. If you’ve ever had an anagram program and run your
friends’ names through it then you know how excited people get when they see what
their name can spell when the letters are rearranged. It’s one of those little things that
computers can do that impresses non-computer people like my mom more than any
amount of awesome 3-D rendering or clever computer animation. This month’s
challenge is to write a fast anagram routine.
The prototype of the function you write is:
/* 1 */
unsigned long Anagram(inputText,
wordList, outputFile)
Str255 inputText;
FILE *wordList;
FILE *outputFile;
InputText is a Pascal string containing the text to anagram. It will be all
lowercase letters (a..z) and may contain spaces, which you should ignore (i.e. your
anagram may contain more or fewer spaces; it doesn’t matter). WordList is a standard
C input stream containing the dictionary of valid words you can use to make your
anagrammed output. The words in the dictionary will be all lowercase and sorted from
‘a’ to ‘z’ (and there will be about 20,000 of them). There is a 0x0D byte between each
word. You should keep reading words from the stream until you reach the end of file.
OutputFile is a standard C output stream that you should write your anagrams to, each
one separated by a 0x0D byte. The return value of the function is the number of unique
anagrams that were sent to the outputFile.
Good luck and Happy New Year!
TWO MONTHS AGO WINNER
Of the 11 entries I received for the Present Packing challenge, nine worked
correctly. Congrats to James Goebel (location unknown) for having the highest average
number of presents packed. James previously won the ASCII85 Encode challenge and
now he is tied in a 3-way tie for the most number of 1st place Challenge showings.
This challenge was judged based on the highest average number of packages
packed. The times and code+data sizes are given for interest only. Numbers in parens
after a person’s name indicate how many times that person has finished in the top 5
places of all previous Programmer Challenges, not including this one.
Name packages time code+data
James Goebel (2) 95.8 4007 2506
Kevin Cutts (1) 94.3 67 10806
Robert Coie 93.8 5 900
Bob Boonstra (4) 93.7 6 5684
Dave Darrah 93.6 6 1002
Paul Pedriana 93.5 5 1442
Stefan Pantke 91.4 121 20552
Allen Stenger (2) 91.0 11439 360
Jeremy Vineyard (1) 67.3 562 664
My apologies for not considering that it would be nice if you could rotate a
present 90 degrees as you packed it. Several people who entered wrote to me and asked
me about that before entering. Unfortunately, Donald Knipp (location unknown) didn’t
ask me and just assumed that he could rotate the presents. But since the storePresProc
had no way of knowing that he had rotated them he ended up putting presents on top of
each other, which invalidated his entry. I’m not happy about disqualifying Donald’s
otherwise clever entry but I must in order to be fair to those who were told they
couldn’t rotate. In the future, I urge everyone to e-mail me if something is ambiguous
or if there are questions about what assumptions you can and cannot make in your
solutions.
Here’s James’ winning solution. My apologies for removing some whitespace and
comments in order to fit it in this column; James’ unedited code is on the source code
disk.
/* 2 */
/* PackPresents() by Clement James Goebel III.
This code accepts a number of presents one after another and
attempts to store as MANY as possible
in its storage area.
This routine starts with an array describing the expected
distribution of data and then slowly changes to use an array
that describes the sizes of observed presents as the process
continues. These arrays are used to decide which presents
are too big and should not be stored as they will cause us
to throw away smaller
presents latter. The routine is slow
and methodical as it trys to pack presents into the smallest
spaces it can find. It also does an ok job of guessing which
packages to discard, a function that might not really be
needed with evenly distributed data sets. But the goal was
to pack the most, so you can't be too careful. The matrix
that keeps track of stored presents contains zeros where
presents are stored, and all other locations contain a value
that represents the amount of free space that is contiguous
to that location. We will always try to fill small holes
first, a better way might be to look for presents that are
half the size of the hole, but that would require many more
special cases. And when placing presents we will always try
to get as many surfaces to touch as possible.
*/
#define WID_DIM 100
#define LEN_DIM 100
#define MIN_GIFT_DIM 5
#define MAX_GIFT_DIM 15
#define LIKES_OTHERS 3
#define LIKES_WALLS 2
#define SPACE_USED 0
#define MEASURING -1
static short sgsGiftsSeen, sgsGiftsStored, sgsLeftmostPresent,
sgsTopmostPresent;
static long sglExpectedCount, sglItemsOnStack,
sglTotalAreaExpected;
static short *sgasStack, *sgasAreasSeen, *sgasAreasExpected;
static long *sgalSpace;
typedef void (*NextPresProc)
(unsigned short *pWidth, unsigned short *pLength );
typedef void (*StorePresProc)
(unsigned short xPos, unsigned short yPos );
void PackPresents( unsigned short usNumGifts,
NextPresProc pNextPresProc, StorePresProc pStorePresProc );
void MyPacker( unsigned short usNumGifts,
long sgaalStorage[WID_DIM][LEN_DIM],
NextPresProc pNextPresProc, StorePresProc pStorePresProc );
// PackPresents()
void PackPresents( unsigned short usNumGifts,
NextPresProc pNextPresProc, StorePresProc pStorePresProc)
{
long w, l, lBytes;
sgsGiftsSeen = sgsGiftsStored = 0;
sglItemsOnStack = 0;
sgsLeftmostPresent = WID_DIM;
sgsTopmostPresent = LEN_DIM;
lBytes = (MAX_GIFT_DIM+1)
* (MAX_GIFT_DIM+1) * sizeof( short );
sgasAreasSeen = (void*)NewPtrClear( lBytes );
sgasAreasExpected = (void*)NewPtrClear( lBytes );
sgasStack = (void*)NewPtrClear( (WID_DIM * LEN_DIM )
* 2 * sizeof( short ) );
sgalSpace = (void*)NewPtrClear( WID_DIM * LEN_DIM
* sizeof( long ) );
// Given the range of inputs we expect to see compute
// the number of presents of each size that we
// expect to be offered.
sgsGiftsSeen = sglExpectedCount = 0;
sglTotalAreaExpected = 0;
for ( w = MIN_GIFT_DIM; w <= MAX_GIFT_DIM; w++ ) {
for ( l = MIN_GIFT_DIM;l<=MAX_GIFT_DIM; l++) {
sgasAreasExpected[ w * l] ++;
sglTotalAreaExpected += w * l;
sglExpectedCount++;
} }
MyPacker( usNumGifts, (void*)sgalSpace,
pNextPresProc, pStorePresProc );
DisposePtr( (Ptr)sgasAreasSeen );
DisposePtr( (Ptr)sgasAreasExpected );
DisposePtr( (Ptr)sgasStack );
DisposePtr( (Ptr)sgalSpace );
}
// Utility routines called by packing routine.
Boolean BestPosition( long aalSpace[WID_DIM][LEN_DIM],
unsigned short usSpaceRemaining, unsigned short usWidth,
unsigned short usLength, short *pusX, short *pusY );
int LargestGiftDesired( unsigned short usSpaceLeft,
unsigned short usTotalGifts, unsigned short usGiftsRemaining,
unsigned short usWidth, unsigned short usLength );
void RecomputeAreas( long aalSpace[WID_DIM][LEN_DIM],
unsigned short *pusSpaceRemaining, int iHoleSize );
// MyPacker()
// After getting each present check to see what the
// expected sizes of the next presents will be and
// pick a largest acceptable size. If the present
// meets the size requirement then find the best
// location for it (presents like to sit amoung
// friends or with thier back to the wall!), and
// store it.
void MyPacker( unsigned short usNumGifts,
long aalGiftStorage[WID_DIM][LEN_DIM],
NextPresProc pNextPresProc, StorePresProc pStorePresProc )
{
unsigned short usSpaceRemaining, usGiftsRemaining;
unsigned short usWidth, usLength;
int iLargestGiftDesired, iArea, i, w, l, iHoleSize;
short X, Y;
usGiftsRemaining = usNumGifts;
usSpaceRemaining = WID_DIM * LEN_DIM;
// Fill storage array with contiguous area values.
// In the beginning all space is empty and contiguous.
for ( w = 0; w < WID_DIM; w++ )
for ( l = 0; l < LEN_DIM; l++ )
aalGiftStorage[w][l] = usSpaceRemaining;
// Get the presents.
while ( usGiftsRemaining ) {
(pNextPresProc)( &usWidth, &usLength );
usGiftsRemaining--;
iLargestGiftDesired = LargestGiftDesired(
usSpaceRemaining, usNumGifts,
usGiftsRemaining, usWidth, usLength );
iArea = usWidth * usLength;
if ( iArea <= iLargestGiftDesired ) {
if ( BestPosition( aalGiftStorage,
usSpaceRemaining, usWidth, usLength, &X, &Y ) ) {
iHoleSize = aalGiftStorage[X][Y];
// Store a gift.
for ( w = 0; w < usWidth; w++ ) {
for ( l = 0; l < usLength; l++ ) {
aalGiftStorage[X+w][Y+l] = SPACE_USED;
} }
pStorePresProc( (unsigned short)X,